package com.algrithom.tree.bst;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Objects;
import java.util.Set;

import com.common.model.TreeNode;
import com.util.TreeOperUtil;

/**
 * 653. 两数之和 IV - 输入 BST
 */
public class Solution4 {
    
    public static void main(String[] args){
        Integer[] list = new Integer[]{5,3,6,2,4,null,null};
        TreeNode<Integer> root = TreeOperUtil.createBstTree(Arrays.asList(list),0,list.length - 1);
        Solution4 solution4 = new Solution4();
        System.out.println(solution4.findTarget(root,5));
    }
    
    public boolean findTarget(TreeNode<Integer> root,int k){
        return find(root,k,new HashSet<>());
    }
    
    private boolean find(TreeNode<Integer> root,int k,Set<Integer> set){
        if (Objects.isNull(root)) {
            return false;
        }
        if (set.contains(k - root.getValue())) {
            return true;
        }
        set.add(root.getValue());
        return find(root.getLeftChild(),k,set) || find(root.getRightChild(),k,set);
    }
}
